#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array)
    {
        vector<int> ret;
        int row = array.size();
        if (row == 0)
            return ret;
        int col = array[0].size();
        int top = 0, bottom = row - 1;
        int left = 0, right = col - 1;

        while (left <= right && top <= bottom)
        {
            for (int i = left; i <= right; ++i)
                ret.push_back(array[top][i]);
            ++top;
            if (top > bottom)
                break;

            for (int i = top; i <= bottom; ++i)
                ret.push_back(array[i][right]);
            --right;
            if (left > right)
                break;

            for (int i = right; i >= left; --i)
                ret.push_back(array[bottom][i]);
            --bottom;
            if (left > bottom)
                break;

            for (int i = bottom; i >= top; --i)
                ret.push_back(array[i][left]);
            ++left;
        }
        return ret;
    }
};


class Solution {
public:
    int bestTiming(vector<int>& prices) {
        int prevMin = INT_MAX;
        int ret = 0;

        for (int i = 0; i < prices.size(); ++i)
        {
            if (prices[i] < prevMin)
            {
                prevMin = prices[i];
            }
            ret = max(ret, prices[i] - prevMin);
        }
        return ret;
    }
};


class Solution
{
    int ret = 0;
    int row, col;
    int dx[2] = { 0,1 };
    int dy[2] = { 1,0 };
    vector<vector<bool>> visit;
public:

    int getSum(int n)
    {
        int sum = 0;
        while (n)
        {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    int wardrobeFinishing(int m, int n, int cnt)
    {
        row = m, col = n;
        visit.resize(m, vector<bool>(n));
        visit[0][0] = true;
        ret++;
        dfs(0, 0, cnt);
        return ret;
    }


    void dfs(int a, int b, int cnt)
    {
        for (int i = 0; i < 2; ++i)
        {
            int x = a + dx[i];
            int y = b + dy[i];

            if (x < row && y < col && !visit[x][y] && (getSum(x) + getSum(y)) <= cnt)
            {
                visit[x][y] = true;
                ret++;
                dfs(x, y, cnt);
            }
        }
    }

};